题解 P3645 【[APIO2015]雅加达的摩天楼】

发表于 | 更新于

$Description$

有$m$只$doge$分布在$n$个摩天大楼上。楼和$doge$都是从$0$开始编号。

每只$doge$初始位置$b[i]$，弹跳力$p[i]$。 它每一次跳会恰好跳$p[i]$个大楼。比如从$x$可以到$x±p[i]$。

现在，$0$号$doge$要把某信息传给$1$号$doge$。对于一只$doge$，若它尚未知道信息，就不能动。 对于一只$doge$，若它已经知道信息，可以选择把信息告诉处于同一位置的$doge$们，或者跳去别的位置。

求最少跳的步数。

$Solution$

先考虑暴力

对于每一只$doge$，我们从$b[i]$ 连边到所有它可以跳到（可以跳好多步）的位置，边权为需要跳的次数。

从$b[0]$跑一下最短路即可。

但是，这样边数太多了。

那么考虑一下分块，把每一座摩天大楼拆成$O(\sqrt{n})$层，第$0$层表示原点,第$j$层代表一步能跳到$b[i]±j$的摩天大楼，如果某座摩天大楼的$p[i]>size$则暴力从该摩天大楼的原点向$b[i]±j$的摩天大楼的原点连边，然后这一层每一个摩天大楼向它能到达的摩天大楼的相同层连双向边，并且每座摩天大楼的每一层都要向该摩天大楼的原点连边，可以保证边数在$n\sqrt{n}$级别左右(视$n,m$同阶)

$Code$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define ll long long
#define re register
#define inf 0x3f3f3f3f
#define N 6000020
#define M 6000020
using namespace std;
struct edge{
    int dis,to,next;
}e[M*9];
inline int read(){
    int x=0,w=0;char ch=getchar();
    while (!isdigit(ch))w|=ch=='-',ch=getchar();
    while (isdigit(ch))x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return w?-x:x;
}
int cnt,head[N],dis[N],inque[N],b[N],p[N],n,m;
inline int id(int x,int y){
    return y*n+x;
}
inline void add(int u,int v,int d){
    e[++cnt].to=v;
    e[cnt].dis=d;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void spfa(int s){
    memset(dis,0x3f,sizeof(dis));
    dis[s]=0;queue<int>q;q.push(s);
    while (!q.empty()){
        int u=q.front();inque[u]=0;q.pop();
        for (int i=head[u];i;i=e[i].next){
            int v=e[i].to;
            if (dis[v]>dis[u]+e[i].dis){
                dis[v]=dis[u]+e[i].dis;
                if (!inque[v])q.push(v),inque[v]=1;
            }
        }
    }
}
signed main(){
    n=read(),m=read();int size=sqrt(n/3);
    for (int i=0;i<m;++i){
        b[i]=read(),p[i]=read();
        if (p[i]>size){//大于size的直接暴力连,边数最多m*sqrt(n)条 
            for (int d=1,j=b[i]-p[i];j>=0;++d,j-=p[i])
                add(id(b[i],0),id(j,0),d);
            for (int d=1,j=b[i]+p[i];j<n;++d,j+=p[i])
                add(id(b[i],0),id(j,0),d);
        }else{
            add(id(b[i],0),id(b[i],p[i]),0);//从每层原点向第p[i]层连边，表示b[i]这个摩天大楼可以跳到b[i]±j的摩天大楼
        }
    }
    for (int j=1;j<=size;++j){
        for (int i=0;i<n;++i){
            if (i+j<n) add(id(i,j),id(i+j,j),1);
            if (i-j>=0)add(id(i,j),id(i-j,j),1);
            add(id(i,j),id(i,0),0);
        }
    }
    spfa(id(b[0],0));
    if (dis[id(b[1],0)]>=inf)puts("-1");
    else printf("%d\n",dis[id(b[1],0)]);
    return 0;
}